package com.dily.study.demo.study;

import org.springframework.stereotype.Component;

import java.util.ArrayList;
import java.util.List;

/**
 * Date: 2022-03-10 星期四
 * Time: 10:19
 * Author: Dily_Su
 * Remark:
 * 排序算法, 以 Integer 为例,从小到大排序
 */
@Component
public class Sorting {
    /**
     * 冒泡排序
     * 时间复杂度: n方
     * 空间复杂度: 1
     *
     * @param list 原始数据
     * @return 排序后的数据
     */
    public List<Integer> bubbleSort(List<Integer> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = 0; j < list.size() - 1 - i; j++) {
                if (list.get(j) > list.get(j + 1)) {
                    Integer temp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, temp);
                }
            }
        }
        return list;
    }

    /**
     * 选择排序
     * 时间复杂度: n方
     * 空间复杂度: 1
     *
     * @param list 原始数据
     * @return 排序后的数据
     */
    public List<Integer> selectionSort(List<Integer> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(minIndex) > list.get(j)) {
                    minIndex = j;
                }
            }
            Integer temp = list.get(i);
            list.set(i, list.get(minIndex));
            list.set(minIndex, temp);
        }
        return list;
    }

    /**
     * 插入排序
     * 时间复杂度: n方
     * 空间复杂度: 1
     *
     * @param list 原始数据
     * @return 排序后的数据
     */
    public List<Integer> insertionSort(List<Integer> list) {
        for (int i = 1; i < list.size(); i++) {
            int preIndex = i - 1;
            Integer current = list.get(i);
            while (preIndex >= 0 && list.get(preIndex) > current) {
                list.set(preIndex + 1, list.get(preIndex));
                preIndex--;
            }
            list.set(preIndex + 1, current);
        }
        return list;
    }

    /**
     * 希尔排序
     * 描述: 改进后的插入排序, 分组插排
     * 时间复杂度: n方
     * 空间复杂度: 1
     *
     * @param list 原始数据
     * @return 排序后的数据
     */
    public List<Integer> shellSort(List<Integer> list) {
        for (int gap = list.size() / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < list.size(); i++) {
                int insertIndex = i;
                Integer current = list.get(i);
                while (insertIndex - gap >= 0 && current < list.get(insertIndex - gap)) {
                    list.set(insertIndex, list.get(insertIndex - gap));
                    insertIndex -= gap;
                }
                list.set(insertIndex, current);
            }
        }
        return list;
    }

    /**
     * 归并排序
     * 描述:
     * 时间复杂度: n方
     * 空间复杂度: 1
     *
     * @param list 原始数据
     * @return 排序后的数据
     */
    public List<Integer> mergeSort(List<Integer> list) {
        if (list.size() < 2) return list;
        int middle = list.size() / 2;
        List<Integer> left = list.subList(0, middle);
        List<Integer> right = list.subList(middle, list.size());
        return mergeList(mergeSort(left), mergeSort(right));
    }

    /**
     * @param left  左边数组
     * @param right 右边数组
     * @return 合并排序后的数组
     */
    private List<Integer> mergeList(List<Integer> left, List<Integer> right) {
        List<Integer> list = new ArrayList<>();
        int leftIndex = 0;
        int rightIndex = 0;
        while (leftIndex < left.size() && rightIndex < right.size()) {
            if (left.get(leftIndex) <= right.get(rightIndex)) {
                list.add(left.get(leftIndex));
                leftIndex++;
            } else {
                list.add(right.get(rightIndex));
                rightIndex++;
            }
        }

        // 当左右列表长度不等时
        if (leftIndex < left.size())
            list.addAll(left.subList(leftIndex, left.size()));

        if (rightIndex < right.size())
            list.addAll(right.subList(rightIndex, right.size()));

        return list;
    }
}
